package exercises.newcoder.solution;

import exercises.newcoder.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * <a href="https://www.nowcoder.com/study/vod/1/1/2?autoplay=1">
 * 第2节 二叉树打印练习题</a>
 *
 * @author or2
 * @Description 层序遍历二叉树
 * @create 2021年09月18日 时间: 11:41
 */
public class ThroughTreeByLevelOrder {

    public int[][] printTree(TreeNode root) {
//        校验输入
        if (root == null) {
            return new int[0][0];
        }

        /*辅助 - 栈 */
        LinkedList<TreeNode> queueAux = new LinkedList<>();
        /*辅助层序 - 当前层的最后结点*/
        TreeNode last = root;
        /*辅助 - 指向下一层的最优结点*/
        TreeNode nLast = root;
        queueAux.addLast(root);

//        记录答案
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> layer = new ArrayList<>();

        while (!queueAux.isEmpty()) {
            TreeNode pop = queueAux.removeFirst();
            layer.add(pop.val);
            if (pop.left != null) {
                queueAux.addLast(pop.left);
//                更新下一行的最后结点
                nLast = pop.left;
            }
            if (pop.right != null) {
                queueAux.addLast(pop.right);
                nLast = pop.right;
            }
            /*发生换行*/
            if (pop == last) {
                ans.add(layer);
                layer = new ArrayList<>();
                last = nLast;
            }
        }

        int sizeOfLayer = ans.size();
        int[][] res = new int[sizeOfLayer][];
        for (int i = 0; i < res.length; i++) {
            layer = ans.get(i);
            res[i] = new int[layer.size()];
            for (int j = 0; j < res[i].length; j++) {
                res[i][j] = layer.get(j);
            }
        }
        return res;
    }
}
